package demo.practice.leetcode;


class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

    public TreeNode setLeft(TreeNode left) {
        this.left = left;
        return this;
    }

    public TreeNode setRight(TreeNode right) {
        this.right = right;
        return this;
    }
}

public class IsBalanced {
    public static void main(String[] args) {

        /*TreeNode treeNode =new TreeNode(3);
        treeNode.left=new TreeNode(9);
        TreeNode nr=new TreeNode(20);
        nr.right = new TreeNode(7);
        nr.left = new TreeNode(15);
        treeNode.right= nr;*/



        TreeNode treeNode =new TreeNode(1).setRight(new TreeNode(2));
        treeNode.left=new TreeNode(2).setLeft(new TreeNode(3).setLeft(new TreeNode(4)) );
        treeNode.left.right=new TreeNode(3);
        treeNode.left.left.right= new TreeNode(4);

        IsBalanced isBalanced = new IsBalanced();
        boolean balanced = isBalanced.isBalanced(treeNode);
        System.out.println(balanced);

    }





    public  boolean  isBalanced(TreeNode root) {

        boolean br = isBalancedThisNode(root);
        if (!br)
            return br;
        else {
            if (root.left != null) {
                br = br && isBalanced(root.left);
            }
            if (root.right != null) {
                br = br && isBalanced(root.right);
            }
            return br;
        }
    }

    /**
     * 单个节点是否是平衡的
     *
     * @param root
     * @return
     */
    public boolean isBalancedThisNode(TreeNode root) {
        if (root == null)
            return true;
        Integer rd = deep(root.right, null);
        Integer ld = deep(root.left, null);

        if (rd - ld > 1 || ld - rd > 1) {
            return false;
        } else {
            return true;
        }
    }


    /**
     * @param node
     * @param d
     * @return
     */
    public Integer deep(TreeNode node, Integer d) {
        if (d == null) {
            d = 0;
        }
        if (node == null)
            return d;
        d++;
        Integer ld = deep(node.left, d);
        Integer rd = deep(node.right,d);
        return ld > rd ? ld : rd;
    }


}
